A flash memory has a unique physical characteristic which is different from a hard disk in that costs of a reading operation and a writing operation are non-uniform.
In the flash memory, a reading and writing unit (page) and a deleting unit (block) are different from each other, temporal costs (reading: 10 μs, writing: 200 μs, and deleting: 2 ms) are different from each other, and generally, the number of deleting times is limited to 100,000 to 1,000,000 per block.
Further, in order to perform the writing operation at the same position, the deleting operation requiring much time needs to be performed. Accordingly, most of NAND flash memory has a flash translation layer to hide direct cost of the deleting operation by performing an out-place update in which writing is performed at a place out of the same position.
As such, since the flash memory has a unique physical characteristic which is different from the hard disk, it is difficult to expect optimum performance in the NAND flash memory system through an existing page replacement algorithm which seeks only a memory hit ratio.
For example, a least recently used (LRU) algorithm is optimized for a storage system on the basis of the hard disk.
The LRU algorithm maintain pages on the memory as a priority list according to the last reference timing and replaces the earliest referenced page when the memory space is insufficient.
The LRU algorithm has good performance in various environments with time locality to be widely used in not only a virtual memory environment but also various fields such as buffer caching and web caching. However, the costs of the reading and writing operations do not consider characteristics of a heterogeneous flash memory and thus, it is difficult to expect the optimal performance in the flash memory system.
Meanwhile, a clean-first LRU (CFLRU) algorithm is a page replacement algorithm in which the memory hit ratio and the costs of the reading and writing operations consider the physical characteristics of the heterogeneous flash memory.
FIG. 5 is a view illustrating a buffer managing method of a CFLRU algorithm in the related art.
Referring to FIG. 5, the CFLRU algorithm basically manages pages by the LRU list and is divided into a working region which is a space storing the relatively recently referenced pages on the LRU list and a clean-first region which is a space storing the relatively earlier referenced pages on the LRU list. In this case, the clean-first region in the CFLRU algorithm is called a window.
Further, in the CFLRU algorithm, the page is divided into a clean page and a dirty page, the clean page is a page in which the content of the page after being uploaded on the memory is not changed, and the dirty page is a page in which the content of the page after being uploaded on the memory is changed.
In addition, in the CFLRU algorithm, the page is replaced in the clean-first region earlier than the working region, and the clean page is replaced earlier than the dirty page in the clean-first region. The replacement of the dirty page generates the writing operation in the flash memory unlike the replacement of the clean page so as to reduce the high-cost writing operation of the flash memory.
Accordingly, referring to FIG. 5, in the existing LRU algorithm, since the earliest referenced page in the list is replaced, the page will be replaced in order of P8→P7→P6→P5. On the contrary, in the CFLRU algorithm, the page will be replaced in order of P7→P5→P8→P6.
However, in the CFLRU algorithm, when replacing the dirty page, the dirty page is replaced by the LRU list, the replacement cost of the dirty page which has an effect on the flash memory is not considered at all.
Meanwhile, in Korea patent registration No. 0941382, “apparatus and method for managing page buffer linked with flash memory, and apparatus and method for changing page of flash memory”, it is proposed a technique that includes a buffer unit which stores data of a page unit read from a flash memory, a buffer management unit which selects replaced data among the data saved in the buffer unit to remove the selected data from the buffer unit if the amount of data saved in the buffer unit reaches a predetermined reference amount, and a page list management unit which generates a page index for a clean page in which a reading operation is performed among the data of the page unit saved in the buffer unit, a clean page list in which a block number including the clean page is written, and a dirty page list for a dirty page in which a writing operation is performed, respectively, and deletes the page index corresponding to the replaced data.
However, in the prior art, the clean page and the dirty page are separately managed to enhance the buffer hit ratio for the dirty page and reduce the entire writing cost. Furthermore, when the data in which the writing operation is performed is replaced, the data included in the same block is replaced together, and thus, there is an advantage in that the lifespan of the flash memory is extended by reducing the number of times performing the deleting operation. However, like the related art, when the dirty page is replaced, the replacement cost of the dirty page which has an effect on the flash memory is not still considered, and thus, the optimal performance is not made in the flash memory system.
Therefore, as the advantage of the present invention, a technique is required, in which the dirty page in the buffer cache is replaced by considering a space to be ensured after evicting and the number of writing times for the flash memory to reduce the writing operation for the flash memory device and improve the performance of the database management system on the basis of the flash memory and the use life span of the storage device.